1. Field of the Invention
The invention relates to the field of computer systems. Specifically, the invention relates to efficient processing of instruction streams which include conditional program flow control instructions, such as branch instructions.
2. Description of Related Art
Many microprocessors employ a technique known as hardware pipelining to increase instruction throughput by processing several instructions through different phases of execution concurrently. To maximize instruction execution efficiency, it is desirable to keep the instruction execution pipeline full (with an instruction being processed in each pipeline stage) as often as possible such that the pipeline produces useful output every clock cycle. However, whenever there has been a transfer of program flow control to another section of software code and instructions have been speculatively fetched and processed and it is determined that these instructions should not have been executed, the output from the pipeline is not useful.
Exceptions and program flow control instructions such as branch instructions, provide examples of how the program flow control can be changed. Branch instructions, which may be conditional or unconditional and may transfer program flow control to a preceding or subsequent code section, are used for frequently encountered situations where a change in program flow control is desired.
A conditional branch instruction determines instruction flow based on the resolution of a specified condition. "If A&gt;B then branch to instruction X" is an example of a conditional branch instruction. In this case, if A&gt;B, program flow control branches to a code section beginning with instruction X, also referred to as the target code section. If A is not greater than B, the instructions sequentially following the branch instruction in the program flow, referred to as the sequential code section, are to be executed.
Because pipelines in some microprocessors can be many stages deep, conditional branch instructions are often fetched before the condition specified in the branch instruction is resolved. In this case, the processor cannot reliably determine whether or not the branch will be taken, and thus, cannot decide from which code section to fetch subsequent instructions. In many processors, branch prediction logic operates to predict the outcome of a particular branch instruction based on a predetermined branch prediction approach. Instructions are then speculatively fetched from either the target code section or the sequential code section based on the prediction indicated by the branch prediction logic.
Although branch prediction accuracy may be improved or tuned by using different branch prediction algorithms, mispredictions still occur. By the time a misprediction is identified, many instructions from the incorrect code section may be in various stages of processing in the instruction execution pipeline. On encountering such a misprediction, instructions following the mispredicted conditional branch instruction in the pipeline (or multiple pipelines) are flushed, and instructions from the other, correct code section are fetched. Flushing the pipeline creates bubbles or gaps in the pipeline. Several clock cycles may be required before the next useful instruction completes execution, and before the instruction execution pipeline produces useful output. Because conditional branch instructions and other similar program flow control instructions are prevalent in software applications code (in some cases, they are encountered as frequently as one branch instruction for every five instructions processed), the cumulative microprocessor performance penalty caused by branch mispredictions can be significant, even where branch prediction accuracy is relatively high. Previous processors do not provide a means for identifying which branch instructions are unlikely to be predicted accurately such that mitigating measures may be taken.
Thus, it is desirable to have a means for reducing or eliminating the performance penalty related to mispredicting the outcome of program flow control operations to provide for more efficient instruction execution. Further, it is desirable to have a means for identifying program flow control instructions that are unlikely to be predicted accurately such that preventive measures may be selectively utilized for the particular instructions that are unlikely to be predicted accurately.